package data_structure.queue;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @Author: lijun
 * @Date: 2018/10/30 16:59
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * 输入: n = 12
 * 输出: 3
 * 解释: 12 = 4 + 4 + 4.
 */
public class NumSquares {

    /**
     * 解法1：使用BFS，效率一般
     * @param n
     * @return
     */
    public int numSquares1(int n) {
        int steps = 0;
        Set<Integer> tmp = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        while (!queue.isEmpty()) {
            steps++;
            for (int k = queue.size(); k > 0; k-- ) {
                int cur = queue.poll();
                Set<Integer> squareArray = getSquareArray(cur);
                for (int square : squareArray) {
                    int m = cur - square;
                    tmp.add(m);
                    if (m == 0) {
                        return steps;
                    }
                }
            }
            queue.addAll(tmp);
        }
        return steps;
    }

    /**
     * 获取完美平方数
     * @param cur
     * @return
     */
    private Set<Integer> getSquareArray(int cur) {
        Set<Integer> squareArray = new HashSet<>();
        for (int i = 1; i <= Math.sqrt(cur); i++) {
            int squares = i*i;
            if (squares <= cur) {
                squareArray.add(squares);
            }
        }
        return squareArray;
    }

    /**
     * 解法二：根据四平方数和定理 可能结果只有 1 2 3 4
     * 时间复杂度 最坏情况 O(sqrt(n)*log(n))
     * @param n
     * @return
     */
    public int numSquares2(int n)
    {
        if (n == 0) return 0;
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        for (int a = 0; a * a <= n; ++a)
        {
            int b = mySqrt(n - a * a);
            if (a * a + b * b == n)
            {
                if (a == 0 || b == 0)
                    return 1;
                else
                    return 2;
            }
        }
        return 3;
    }

    /**
     * 牛顿下山法进一步优化sqrt 减少double计算
     * 复杂度< O(log(n))
     * @param x
     * @return
     */
    private int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int result = x / 2;
        while (!(result < x / result && (result + 1) > x / (result + 1) || result == x / result)) {
            int mid_value = ((result + x / result) / 2);
            if (mid_value == result) return result;
            result = mid_value;
        }
        return result;
    }

    public static void main(String[] args) {
        LocalDateTime startTime = LocalDateTime.now();

        System.out.println(new NumSquares().numSquares2(8935));

        Duration duration = Duration.between(startTime, LocalDateTime.now());
        System.out.println(duration.toMillis() + "ms");
    }

}
